The invention relates to a method for decoding a two-dimensional optical code.
In particular, the invention relates to a method for decoding a two-dimensional optical code in which decoding the code, based on a single acquired image, is not successful. For example, the method has particular application for reading two-dimensional optical codes positioned on reflecting surfaces.
By the term “two-dimensional optical code” a set of graphic marks is intended, located on a label or directly on a product, by means of which information is associated with a surface divided into white, black or coloured cells, arranged in one or more directions. Some of the most common two-dimensional symbologies on the market are the PDF-417, QR Code or Aztec and two-dimensional codes of different symbologies may differ by shape (for example square or rectangular), and/or by the manner of coding data (for example a matrix arrangement or a superimposed barcodes), and/or by the quantity of stored data.
All the two-dimensional codes, even if they refer to different types of symbologies, enable a large number of “data of interest” to be coded in a short space through a combination of suitably arranged unitary information. It is pointed out that the term “relevant information” or “data of interest” indicates any information or information set that is coded and stored in a two-dimensional code.
A two-dimensional optical code is formed by a total number of codewords (identified below in the text and/or in the figures also by CWs) and each codeword (identified below in the text and/or in the figures also by CW), which represents an alphanumeric value coded in a certain arrangement of elementary white, black or coloured cells, constitutes the unitary information contained in the code.
In addition to the codewords necessary for forming the data of interest, a two-dimensional optical code also comprises redundant codewords, which enable reading errors to be detected and possibly corrected by specific algorithms for self-correcting the errors, which are illustrated in greater detail below.
In order to decode a two-dimensional code, the image on which the code is positioned is analysed by known image analysis methods for obtaining a set of codeword values assigned to the code, equal to the total number of codewords from which the two-dimensional code is formed. Each codeword can be identified and thus take on a numeric value, if the codeword is recognised, or vice versa can take on an undefined value if the codeword is not recognised, for example because the portion of image in which the codeword is positioned was damaged at the moment of acquisition of the image.
The algorithms for error detection and self-correction provide both the possibility of filling codewords of undefined value, otherwise known as holes, and of correcting erroneous codewords.
The algorithm for error detection and self-correction that is currently used by all the main two-dimensional symbologies is the Reed Solomon algorithm (identified below in the text and/or in the figures also as RS), but further algorithms for error detection and self-correction are also known, such as, for example, the “turbo code” or the “convolutional code”. The term “algorithm for error detection and self-correction” means below and without restrictions either the Reed Solomon code, or the “turbo code” or the “convolutional code”.
Owing to the application of algorithms for error detection and self-correction, it occurs that decoding of a two-dimensional code, which comprises analysing the image on which the code is positioned, identifying the codeword values that are part of the code and checking the code by applying an algorithm for detection and self-correction of errors, such as, for example, the RS algorithm, can take place successfully also if the analysed image has deteriorated partially and thus the value of certain codewords is erroneous or undefined.
In other words, a two-dimensional code can be decoded by a reader of optical codes even if it is partially unusable, for example because it is covered or damaged by spots, abrasions or also if it is positioned on reflecting surfaces. For example, an image of an optical code positioned on a reflecting surface is often partially damaged due to bright spots in some zones of the image.
Nevertheless, when the unusable or damaged image portion of the code becomes excessive, the RS algorithm for error detection and self-correction is not able, by analysing a single image, to decode successfully the coded data of interest and it is thus necessary to analyse also further images of the same code.
In the case of manual readers, the user, by not receiving any good reading notice, tends to move or orient differently the reader to acquire an image that is lighted differently from the preceding image. On the other hand, in the case of the fixed reading systems, the object that carries the code is moved by an external device or by the user, with a random or guided movement, to ensure that in the successively acquired images high luminosity zones, or vice versa poorly lit zones are situated in different positions.
Combining the information that comes from successive images is known, in order to supplement codewords that are not recognised in an image arising from an acquisition, with corresponding codewords recognised in a further image, deriving from a further acquisition, in order to obtain information that is sufficient to enable the entire code to be decoded. From a set of codewords and from a further set of codewords a set of combined codewords is obtained for decoding the code.
U.S. Pat. No. 7,344,080 discloses a coded information reader provided with a guide in which a support (typically a plasticised card) containing a two-dimensional code is moved with respect to a device for capturing and decoding images. The device captures a series of images that may contain only a part of the code or the entire code, and, subsequently, the images are combined to obtain complete decoding of the code by a combination method, which recalls a method illustrated in U.S. Pat. No. 5,821,519, which is a combination method relating to a linear code.
In particular, the methods for decoding coded information based on the combination of information coming from several partial readings of the same linear code are commonly indicated as “stitching” methods.
U.S. Pat. No. 5,821,519 relates to “stitching” linear bar codes and is based on a reconstruction of a barcode achieved starting with images containing respective partial linear scans. In each analysed image, a sequence of characters is identified and amongst the various images a superimposed zone is sought, possibly of preset length, that contains an identical information fragment, by means of which to combine the partial code fragments. As the linear codes always comprise a “start” character, a “stop” character or a “localisation character”, also these characters are sought in the various partial scans in order to store each character identified in the correct position in the reconstructed set of characters with which to decode the barcode.
Further, an “expected reliability value” (ER) is assigned to each character the value of which is identified, to ensure that the reconstructed barcode contains the identified characters having the highest ER value. The “stitching” method disclosed requires above all that all the characters be identified inasmuch as, otherwise, it is not possible to decode the barcode.
Applying the “stitching” method disclosed by U.S. Pat. No. 5,821,519 relating to linear bar codes and which is specific for linear bar codes, nevertheless poses some problems if applied to the two-dimensional bar codes.
First of all, particular repeated characters do not exist in a two-dimensional code, by means of which it is possible to identify superimposed zones that are usable for combining the partial code portions. Further, the decoding method of U.S. Pat. No. 5,821,519 fails if the reconstructed set of characters comprises characters with an undefined value. This logic is certainly not applicable to a two-dimensional code, inasmuch, as said previously, a two-dimensional code could be decoded even if it has undefined codewords.
Further, basing acceptance of a value of a character on an expected reliability (ER) value, favouring the characters with the highest ER value, introduces a probabilistic choice and characters with an erroneous value could be introduced into the reconstructed set of characters inasmuch as they are very probable.
One property of the Reed Solomon algorithm is that it operates with greater efficiency with an unknown codeword rather than with an erroneous codeword because, in order to regenerate the value of a missing codeword, the Reed Solomon algorithm considers just one additional codeword whereas for correcting a codeword the value of which is erroneous, the Reed Solomon algorithm has to consider two additional codewords. Thus, a decoding method of a two-dimensional code deriving from known “stitching” methods relating to linear codes is not optimal and introduces limitations to the decoding itself, inasmuch as it tends to fill all the codewords, also accepting erroneous values and thus makes the operation of the Reed Solomon algorithm less efficient. All this is reflected, in the case of manual readers or in the case of fixed vision systems, into long waiting times for the good reading message, which overall makes decoding slower.
The object of the present invention is to provide a decoding method for decoding an optical code, which is particularly efficient for decoding a two-dimensional optical code if decoding of the code based on a single acquired image is not successful and it is necessary to consider the combination of several images.
A further object of the present invention is to make decoding of a two-dimensional code fast by exploiting the properties of the algorithms for error detection and self-correction.
According to the invention, there is provided a decoding method as defined in claim 1.
Owing to the invention, a decoding method is provided that is particularly dedicated to two-dimensional optical codes that comprises a combination method of images according to which in the presence of corresponding codewords, the values of which are different, it assigns an undefined value to a corresponding codeword of the combined set, if this codeword of the combined set is evaluated as unreliable.
According to one embodiment, a codeword is judged to be reliable if the same value is identified for a number of times at least equal to a predetermined reliability threshold value, this threshold value being in particular greater than 1.
In this manner, the probability of having an erroneous codeword is decreased as a codeword is required to be seen to be always identical to itself for a certain number of times in succession before being marked as being reliable. In the case of values of contrasting codewords, if the reliability threshold for the codeword is not reached, it is preferred to assign an undefined value to the codeword.
Further, introducing undefined values into the set of combined values makes it more probable that the algorithm for error detection and self-correction is successful inasmuch, as said previously, this algorithm is more efficient in determining the value of missing codewords rather than correcting erroneous codewords.